package leetcode.editor.cn;

//给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。 
//
// 
//
// 
// 
// 示例 1： 
//
// 
//输入：s = "(()"
//输出：2
//解释：最长有效括号子串是 "()"
// 
//
// 示例 2： 
//
// 
//输入：s = ")()())"
//输出：4
//解释：最长有效括号子串是 "()()"
// 
//
// 示例 3： 
//
// 
//输入：s = ""
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 3 * 10⁴ 
// s[i] 为 '(' 或 ')' 
// 
// 
// 
// Related Topics 栈 字符串 动态规划 👍 1783 👎 0

import java.util.Arrays;
import java.util.Stack;

//Java：【32】 - 最长有效括号
public class LongestValidParentheses_32{
    public static void main(String[] args) {
        Solution solution = new LongestValidParentheses_32().new Solution();
                // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int longestValidParentheses(String s) {
        // 动态规划
        if(s.length()==0)  return 0;
        char[]  chars = s.toCharArray();
        int[] dp = new int[chars.length];
        int res=0;
        for (int i = 1; i < chars.length; i++) { // 对于0位不需要管，因为不可能
            if(chars[i]==')'){
                if(chars[i-1]=='('){
                    dp[i] = (i>=2?dp[i-2]:0)+2;
                    /**
                     * index     i-1    i
                     * str      (       )
                     * dp       0       =dp[i-1]+2
                     */
                }else if(i-dp[i-1]>0 && chars[i-dp[i-1]-1]=='(')
                    dp[i] = dp[i-1]+ ((i-dp[i-1])>=2?dp[i-dp[i-1]-2]:0)+2;
                /**
                 * index     i-dp[i-1]-2   i-dp[i-1]-1   i-dp[i-1]   i-1    i
                 * str   (   )               (           (           )      )
                 * dp    0   2               0           0           2      = dp[i-1] + dp[i-dp[i-1]-2] + 2
                 * 即被自己这一对包括的加上自己，再加上前面满足的
                 */

                res = Math.max(dp[i],res);
            }
        }
        System.out.println(Arrays.toString(dp));
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
public int longestValidParentheses(String s) {
        // 栈
    if(s.length()==0)  return 0;
    char[]  chars = s.toCharArray();
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    int res = 0;
    for (int i = 0; i < chars.length; i++) {
        char ch = chars[i];
        if(ch==')'){
            stack.pop(); // 有相互匹配，此时保证栈中有值
            if (stack.isEmpty()){
                stack.push(i); // 栈为空时放入当前的坐标，用于计算
            }else {
                res = Math.max(res, i-stack.peek()); // 能够相互匹配，计算得到较大值
            }
        }else {
            stack.push(i);  // 放入‘(’ 的下标
        }
    }
    return res;
}
}
